// https://leetcode.cn/problems/partition-list/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 使用两个虚拟头节点分别构建小于x和大于等于x的链表
// 2. 遍历原链表，根据节点值分配到对应链表
// 3. 连接两个链表，确保链表末尾指向nullptr
// 4. 时间复杂度：O(N)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include "LinkedListUtils.h"

class Solution 
{
public:
    ListNode* partition(ListNode* head, int x) 
    {
        if (head == nullptr) return nullptr;

        ListNode* dummy1 = new ListNode(-1);
        ListNode* dummy2 = new ListNode(-1);
        
        auto cur1 = dummy1, cur2 = dummy2;
        auto cur = head;

        while (cur != nullptr)
        {
            if (cur->val < x)
            {
                cur1->next = cur;
                cur1 = cur1->next;
            }
            else
            {
                cur2->next = cur;
                cur2 = cur2->next;
            }
            cur = cur->next;
        }

        cur1->next = dummy2->next;
        cur2->next = nullptr;

        auto result = dummy1->next;

        delete dummy1;
        delete dummy2;

        return result;
    }
};

int main()
{
    vector<int> nodes1 = {1,4,3,2,5,2};
    vector<int> nodes2 = {2,1};
    int x1 = 3, x2 = 2;

    Solution sol;

    auto l1 = createLinkedList(nodes1);
    auto l2 = createLinkedList(nodes2);

    auto r1 = sol.partition(l1, x1);
    auto r2 = sol.partition(l2, x2);

    printLinkedList(r1);
    printLinkedList(r2);

    return 0;
}